package com.algrithom.dp;

import java.util.Objects;

public class Solution2 {
    
    public static void main(String[] args){
        String str1 = "mhunuzqrkzsnidwbun";
        String str2 = "szulspmhwpazoxijwbq";
        System.out.println(maxLenLcs(str1,str2));
    }
    
    private static int maxLenLcs(String str1,String str2){
        if (Objects.isNull(str1) || Objects.isNull(str2)) {
            return 0;
        }
        int len1 = str1.length();
        int len2 = str2.length();
        return dp(str1,str2,len1 - 1,len2 - 1);
    }
    
    private static int dp(String str1,String str2,int i,int j){
        if (i == -1 || j == -1) {
            return 0;
        } else if (str1.charAt(i) == str2.charAt(j)) {
            return dp(str1,str2,i - 1,j - 1) + 1;
        } else {
            return Math.max(dp(str1,str2,i - 1,j),dp(str1,str2,i,j - 1));
        }
    }
    
    private static int dpOper(String text1,String text2,int len1,int len2){
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
}
